package com.jumper.cwolf.leetcode;

import cn.hutool.json.JSONObject;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 描述：Trie
 * @author cwolf
 * @version 1.0
 * @date 2021/4/1 14:44
 */
public class Trie {


    public class MyNode{
        private boolean exist;
        private MyNode[] words = new MyNode[26];

        public boolean isExist() {
            return exist;
        }
        public void setExist(boolean exist) {
            this.exist = exist;
        }


        public boolean containKey(char key){
            return words[key-'a']!=null;
        }

        public void put(char key,MyNode node){
            words[key-'a'] = node;
        }

        public MyNode get(char key){
            return words[key-'a'];
        }

    }
    //根节点
    MyNode root = new MyNode();


    /** Initialize your data structure here. */
    public Trie() {
    }
    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] cs = word.toCharArray();
        MyNode node = root;
        for (int i=0;i<cs.length;i++){
            char c = cs[i];
            if(node.containKey(c)){
                node = node.get(c);
            }else{
                MyNode nodeNext = new MyNode();
                node.put(c,nodeNext);
                node = nodeNext;
            }
        }
        node.setExist(true);

    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        char[] cs = word.toCharArray();
        MyNode node = root;
        int i = 0;
        for(;i<cs.length;i++){
            char c = cs[i];
            MyNode myNode = node.get(c);
            if(myNode==null){
                return false;
            }
            node = myNode;
        }

        return node.isExist();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        char[] cs = prefix.toCharArray();
        MyNode node = root;
        int i = 0;
        for(;i<cs.length;i++){
            char c = cs[i];
            MyNode myNode = node.get(c);
            if(myNode==null){
                return false;
            }
            node = myNode;
        }
        return true;

    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("adple");
        boolean apple = trie.search("apple");// 返回 True
        boolean app = trie.search("app");// 返回 False
        boolean app1 = trie.startsWith("app");// 返回 True
        trie.insert("app");
        boolean app2 = trie.search("app");
        System.out.println(apple+""+app+""+app1+app2);

    }
}

